import java.util.Arrays;

public class Algorithm {

    /*public static void main(String[] args) {
        int[] arr = {1,3,5,7,2,4,6,8};
        int[] ret = smallestK(arr, 4);
    }

    public static int[] smallestK(int[] arr, int k) {
        if (arr == null || k == 0) {
            return new int[0];
        }
        int num = process(arr, 0, arr.length - 1, k - 1);
        int[] ret = new int[k];
        int j = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] < num) {
                ret[j++] = arr[i];
            }
        }
        if (j < k - 1) {
            for (;  j < k; j++) {
                ret[j] = num;
            }
        }
        return ret;
    }

    public static int process(int[] arr, int l, int r, int index) {
        if (l == r) {
            return arr[l];
        }
        int pivot = arr[l + (int)(Math.random() *(r - l + 1)) ];
        int[] p = partition(arr, l, r, pivot);
        if (index >= p[0] && index <= p[1]) {
            return arr[index];
        } else if (index < p[0]) {
            return process(arr, l, p[0] - 1, pivot);
        } else {
            return process(arr, p[0] + 1, r, pivot);
        }

    }

    public static int[] partition(int[] arr, int l, int r, int pivot) {
        int less = l - 1, more = r + 1;
        int cur = l;
        while (cur < more) {
            if (arr[cur] < pivot) {
                swap(arr, ++less, cur++);
            } else if (arr[cur] > pivot) {
                swap(arr, --more, cur);
            } else {
                cur++;
            }
        }
        return new int[] {less + 1, more - 1};
    }

    public static void swap(int[] arr, int p, int q) {
        int t = arr[p];
        arr[p] = arr[q];
        arr[q] = t;
    }

     */

    /*public static int[] getLeastNumbers(int[] arr, int k) {
        if (k == 0 || arr == null) {
            return new int[0];
        }
        int num = process(arr, 0, arr.length - 1, k - 1);
        int[] ret = new int[k];
        int j = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] < num) {
                ret[j++] = arr[i];
            }
        }
        if (j < arr.length - 1) {
            for(; j < k; j++) {
                ret[j] = num;
            }
        }
        return ret;
    }

    public static int process(int[] arr, int l, int r, int index) {
        if (l == r) {
            return arr[l];
        }
        int pivot = medianOfMedians(arr, l, r);
        int[] range = partition(arr, l, r, pivot);
        if (index >= range[0] && index <= range[1]) {
            return arr[index];
        } else if (index < range[0]) {
            return process(arr, l, range[0] - 1, index);
        } else {
            return process(arr, range[0] + 1, r, index);
        }
    }

    public static int medianOfMedians(int[] arr, int l, int r) {
        int size = r - l + 1;
        int offSet = size % 5 == 0 ? 0 : 1;
        int[] mArr = new int[size / 5 + offSet];
        for (int team = 0; team < mArr.length; team++) {
            int teamFirst = l + team * 5;
            mArr[team] = getMedian(arr, teamFirst, Math.min(r, teamFirst + 4));
        }
        return process(mArr, 0, mArr.length - 1, mArr.length / 2);
    }

    public static int[] partition(int[] arr, int l, int r, int pivot) {
        int less = l - 1, more = r + 1;
        int cur = l;
        while (cur < more) {
            if (arr[cur] < pivot) {
                swap(arr, ++less, cur++);
            } else if (arr[cur] > pivot) {
                swap(arr, --more, cur);
            } else {
                cur++;
            }
        }
        return new int[] {less + 1, more - 1};
    }

    public static int getMedian(int[] arr,int l, int r) {
        insertionSort(arr, l, r);
        return arr[(r + l) / 2];
    }

    public static void insertionSort(int[] arr, int l, int r) {
        for (int i = l; i<= r; i++) {
            for (int j = i - 1; j >= l && arr[j] > arr[j+1]; j--) {
                swap(arr, j, j+1);
            }
        }
    }

    public static void swap(int[] arr, int p, int q) {
        int t = arr[p];
        arr[p] = arr[q];
        arr[q] = t;
    }

    public static void main(String[] args) {
        int[] arr ={0,0,2,3,2,1,1,2,0,4};
        int[] ret = getLeastNumbers(arr, 10);
        System.out.println(Arrays.toString(ret));
    }

     */

    /*public static char[] getManacherString(String str) {
        char[] charArr = str.toCharArray();
        char[] res = new char[str.length() * 2 + 1];
        int index = 0;
        for (int i = 0; i != res.length; i++) {
            res[i] = (i & 1) == 0 ? '#' : charArr[index++];//偶数放‘#’，计数放原来内容
        }
        return res;
    }

    public static String Manacher(String s) {
        char[] str = getManacherString(s);
        int R = -1, C = -1;//中心 && 半径
        int[] pArr = new int[str.length];//回文串长度
        int max = -1;
        int maxIndex = -1;
        for (int i = 0; i < str.length; i++) {
            pArr[i] = R > i ? Math.min(pArr[2 * C - i], R - i) : 1;//i再中心里面吗？
            while (i + pArr[i] < str.length && i - pArr[i] > -1) {
                if (str[i + pArr[i]] == str[i - pArr[i]]) {
                    pArr[i]++;
                } else {
                    break;
                }
            }
            if (i + pArr[i] > R) {
                R = i + pArr[i];
                C = i;
            }
        }

        for (int i = 0; i < pArr.length; i++) {
            if (pArr[i] > max) {
                max = pArr[i];
                maxIndex = i;
            }
        }
        max -= 2;
        String ret = "";
        int k = maxIndex - max;
        while (max >= 0) {
                ret += str[k];
                k += 2;
                --max;
        }
        return ret;
    }


    public static void main(String[] args) {
        String s = "babad";
        String maxPlength = Manacher(s);
        System.out.println(maxPlength);
    }

     */

    /*public static int[] getNext(char[] match) {
        if (match.length == 1) {//特殊情况
            return new int[] {-1};
        }
        int[] next = new int[match.length];
        //初始条件
        next[0] = -1;
        next[1] = 0;
        int cn = 0, i = 2;
        while (i < match.length) {
            if (match[cn] == match[i - 1]) {//字符如果相匹配
                next[i++] = ++cn;
            } else if (cn > 0) {//往前走
                cn = next[cn];
            } else {//说明任何一个都不匹配，则该位置的“指标”是0；
                next[i++] = 0;
            }
        }
        return next;
    }

    public static boolean KMP (String s, String m) {
        if (s == null || m == null || m.length() < 1 || s.length() < m.length()) {
            return false;
        }
        char[] str = s.toCharArray();
        char[] match = s.toCharArray();
        int[] next = getNext(match);//获取“指标数组”；
        int x = 0, y = 0;
        while (x < str.length && y < match.length) {
            if (str[x] == match[y]) {//相匹配，继续往后走
                x++;
                y++;
            } else if (y == 0) {//如果y走到了0位置，则说明没有一个字符和x匹配，x往后走
                x++;
            } else {//y往前移动看有没有匹配
                y = next[y];
            }
        }
        return y == match.length;
    }

    public static void main(String[] args) {
        String s = "aabbccddafjandfjlknadfjlkhwoiqhfnoqnfjl";
        String m = "jlkhwoi";
        boolean res = KMP(s, m);//检查是否是子串
        System.out.println(res);
    }

     */

    /*public static void swap(int[] arr, int o1, int o2) {
        int t = arr[o1];
        arr[o1] = arr[o2];
        arr[o2] = t;
    }

    public static int[] partition(int[] arr, int l, int r, int pivot) {
        int less = l - 1, more = r + 1;
        int cur = l;
        while (cur < more) {
            if (arr[cur] < pivot) {
                swap(arr, ++less, cur++);
            } else if (arr[cur] > pivot) {
                swap(arr, --more ,cur);
            } else {
                cur++;
            }
        }
        return new int[] {less + 1, more - 1};
    }

    public static int process(int[] arr, int l, int r, int index) {
        if (l == r) {//如果l == r，说明arr[l]就是我们要找的数字
            return arr[l];
        }
        int pivot = arr[l + (int)((r - l + 1) * Math.random())];//随机取一个数
        int[] range = partition(arr, l, r, pivot);//做partition找边界
        if (index >= range[0] && index <= range[1]) {//正好命中
            return arr[index];
        } else if (index < range[0]) {//小于左边界
            return process(arr, l, range[0] - 1, index);
        } else {//大于右边界
            return process(arr, range[1] + 1, r, index);
        }
    }

    public static int kthMin(int[] arr, int k) {
        return process(arr, 0, arr.length - 1, k-1);
    }

    public static void main(String[] args) {
        int[] arr = {1,3,5,7,2,4,6,8};
        int k = kthMin(arr, 4);//调用函数
        System.out.println(k);
    }

     */

    /*public static void swap(int[] arr, int o1, int o2) {
        int t = arr[o1];
        arr[o1] = arr[o2];
        arr[o2] = t;
    }

    public static int[] partition(int[] arr, int l, int r, int pivot) {
        int less = l - 1, more = r + 1;
        int cur = l;
        while (cur < more) {
            if (arr[cur] < pivot) {
                swap(arr, ++less, cur++);
            } else if (arr[cur] > pivot) {
                swap(arr, --more ,cur);
            } else {
                cur++;
            }
        }
        return new int[] {less + 1, more - 1};
    }

    public static int medianOfMedians(int[] arr, int l, int r) {
        int size = r - l + 1;
        int offSet = size % 5 == 0 ? 0 : 1;//看要分几组
        int[] mArr = new int[size / 5 + 1];
        for (int team = 0; team < mArr.length; team++) {
            int teamFirst = l + team * 5;
            mArr[team] = getMedian(arr, teamFirst, Math.min(teamFirst + 4, r));//分好组之后获得中位数
        }
        return bfprt(mArr, 0, mArr.length - 1, mArr.length / 2);//获得中位数的中位数
    }

    public static int getMedian(int[] arr, int l, int r) {
        insertionSort(arr, l, r);
        return arr[(l + r) / 2];//中位数
    }

    public static void insertionSort(int[] arr, int l, int r) {//常数项很小的插入排序
        for (int i = l + 1; i <= r; i++) {
            for (int j = i - 1; j >= l && arr[j] > arr[j + 1]; j--) {
                swap(arr, j, j + 1);
            }
        }
    }

    public static int bfprt(int[] arr, int l, int r, int index) {
        if (l == r) {
            return arr[l];
        }
        int pivot = medianOfMedians(arr, l, r);//天选之子
        int[] range = partition(arr, l, r, pivot);
        if (index >= range[0] && index <= range[1]) {
            return arr[index];
        } else if (index < range[0]) {
            return bfprt(arr, l, range[0] - 1, index);
        } else {
            return bfprt(arr, range[1] + 1, r, index);
        }
    }

    public static int kthMin(int[] arr, int k) {
        return bfprt(arr, 0, arr.length - 1, k - 1);
    }

    public static void main(String[] args) {
        int[] arr = {1,4,2,5,3,7,6,8};
        int k = kthMin(arr, 5);
        System.out.println(k);
    }

     */

    /*public static char[] manacherString(String str) {
        char[] arr = str.toCharArray();
        char[] ret = new char[2 * str.length() + 1];
        int index = 0;
        for (int i = 0; i < ret.length; i++) {
            ret[i] = (i & 1) == 0 ? '#' : arr[index++];
        }
        return ret;
    }

    public static int Manacher(String str) {
        char[] arr = manacherString(str);//处理字符串
        int[] pArr = new int[arr.length];//最大回文半径存储
        int R = -1 , C = -1;//设置默认值
        int max = -1;
        /**
         * case1 ： i再r边界外
         * case2 ： i 与 i关于c对称点i'的回文半径全在r范围内
         * case3 ： i’的回文半径再r外
         * case4 ：i'的回文半径与r重合
         */

        /*for (int i = 0; i < arr.length; i++) {
            pArr[i] = R > i ? Math.min(R -i, pArr[2 * C - i]) : 1;//与i对应的i‘的最大回文半径
            while (i + pArr[i] < arr.length && i - pArr[i] > -1) {//四个case的情况过滤
                if (arr[i + pArr[i]] == arr[i - pArr[i]]) {
                    pArr[i]++;
                } else {
                    break;
                }
            }
            if (i + pArr[i] > R) {//中心更新
                R = i + pArr[i];
                C = i;
            }
            max = Math.max(max, pArr[i]);
        }
        return max - 1;
    }


    public static void main(String[] args) {
        String str = "aaabbbbcacbbasqjofhjonaduuuuuvuuuuu";//uuuuuvuuuuu
        int maxPlenght = Manacher(str);
        System.out.println(maxPlenght);
    }
    */


    public static void main(String[] args) {
        System.out.println("No pain , no gain");
    }

}
